package com.zll.study.栈;

import java.util.LinkedList;

/**
 * 描述
 * 给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
 * 1.左括号'('必须有对应的右括号')'
 * 2.右括号')'必须有对应的左括号'('
 * 3.左括号必须在对应的右括号前面
 * 4.*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符
 * 5.空字符串也视为合法的括号字符串
 *
 * 输入："((*)"
 * 返回值：true
 *
 * 输入："(((*)"
 * 返回值：false
 *
 */
public class NC175合法的括号字符串 {
    public static void main(String[] args) {
        System.out.println(isValidString("(((***)))"));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public static boolean isValidString (String s) {
        //待消除左括号的最小个数
        int minCount=0;
        //待消除左括号的最大个数
        int maxCount=0;
        int n=s.length();
        for(int i=0;i<n;i++){
            char c=s.charAt(i);
            //如果是左括号，minCount和maxCount均加1
            if(c=='('){
                minCount++;
                maxCount++;
            }
            //如果是右括号，minCount和maxCount均减1
            else if(c==')'){
                if(minCount>0){
                    minCount--;
                }
                if(maxCount==0){
                    return false;
                }
                maxCount--;
            }
            //如果是*号，minCount减1，maxCount加1
            else{
                if(minCount>0){
                    minCount--;
                }
                maxCount++;
            }
        }
        //只要minCount为0，说明左括号能全部抵消掉，字符串合法
        return minCount==0;
    }

}
